package leetcode;

//编写一个程序，通过已填充的空格来解决数独问题。
//一个数独的解法需遵循如下规则：
//数字 1-9 在每一行只能出现一次。
//数字 1-9 在每一列只能出现一次。
//数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
//空白格用 '.' 表示。

import java.util.Arrays;

public class problems_037 {

    public static void main(String[] arge){
        char[][] param  = {
                {'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'},
        };
        new Solution().solveSudoku(param);
    }
    static class Solution {
        public void solveSudoku(char[][] board) {
            // 设置
            setPoint(board, 0);
            // 显示
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(board[i][j]);
                }
                System.out.print("\n");
            }
        }

        // 点设置
        private boolean setPoint(char[][] board, int index) {
            if(index >= 9*9){
                return true;
            }
            int x = index % 9; // 判断位置X
            int y = index / 9; // 判断位置Y
            if (board[x][y] != '.') return setPoint(board, index + 1);
            // 取得可设置点
            char[] able = getAble(board, x, y);
            if(null == able) return false;
            // 可处理数字
            for (int i = 0; i < able.length; i++) {
                if ( ' ' == able[i]) continue;
                board[x][y] = able[i];
                if(setPoint(board, index + 1)) return true;
            }
            board[x][y] = '.';
            // 设置下一点
            return false;
        }
        // 取得可设置数字
        private char[] getAble(char[][] board, int x, int y) {
            char[] able = {'1','2','3','4','5','6','7','8','9'};

            // 判断同一行是否合法
            for (int i = 0; i < board.length; i++) {
                if (board[x][i] == '.') continue;
                int charIndex = index(able, board[x][i]);
                if(charIndex == -1) continue;
                able[charIndex] = ' ';
            }
            // 判断同一列是否合法
            for (int i = 0; i < board.length; i++) {
                if (board[i][y] == '.') continue;
                int charIndex = index(able, board[i][y]);
                if(charIndex == -1) continue;
                able[charIndex] = ' ';
            }
            // 判断九宫格内是否合法
            int beginX = 3 * (x / 3);
            int beginY = 3 * (y / 3);
            for (int i = beginX; i < beginX + 3; i++) {
                for (int j = beginY; j < beginY + 3; j++) {
                    if (board[i][j] == '.') continue;
                    int charIndex = index(able, board[i][j]);
                    if(charIndex == -1) continue;
                    able[charIndex] = ' ';
                }
            }
            return able;
        }
        // char的index
        private int index(char[] arr, char obj) {
            for (int i = 0; i < arr.length; i++) {
                if(arr[i] == obj) return i;
            }
            return -1;
        }
    }
}
